// 原始记录  第一次运行成功的代码没有调试
#include <stdio.h>
#include <stdlib.h>

#define ERROR -1

typedef int ElementType;
typedef enum { push, pop, inject, eject, end } Operation;
typedef enum { false, true } bool;
typedef int Position;

typedef struct QNode *PtrToQNode;
struct QNode {
    ElementType *Data;      /* 存储元素的数组   */
    Position Front, Rear;   /* 队列的头、尾指针 */
    int MaxSize;            /* 队列最大容量     */
};
typedef PtrToQNode Deque; 

Deque CreateDeque( int MaxSize )
{   /* 注意：为区分空队列和满队列，需要多开辟一个空间 */
    Deque D = (Deque)malloc(sizeof(struct QNode));
    MaxSize++;
    D->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    D->Front = D->Rear = 0;
    D->MaxSize = MaxSize;
    return D;
}

bool Push( ElementType X, Deque D );
ElementType Pop( Deque D );
bool Inject( ElementType X, Deque D );
ElementType Eject( Deque D );

Operation GetOp();          /* 裁判实现，细节不表 */
void PrintDeque( Deque D ); /* 裁判实现，细节不表 */

int main()
{
    ElementType X;
    Deque D;
    int N, done = 0;

    scanf("%d", &N);
    D = CreateDeque(N);
    while (!done) {
        switch(GetOp()) {
        case push: 
            scanf("%d", &X);
            if (!Push(X, D)) printf("Deque is Full!\n");
            break;
        case pop:
            X = Pop(D);
            if ( X==ERROR ) printf("Deque is Empty!\n");
            else printf("%d is out\n", X);
            break;
        case inject: 
            scanf("%d", &X);
            if (!Inject(X, D)) printf("Deque is Full!\n");
            break;
        case eject:
            X = Eject(D);
            if ( X==ERROR ) printf("Deque is Empty!\n");
            else printf("%d is out\n", X);
            break;
        case end:
            PrintDeque(D);
            done = 1;
            break;
        }
    }
    return 0;
}
/*
双端队列，请编写例程实现下列操作：

Push(X,D)：将元素X插入到双端队列D的头；
Pop(D)：删除双端队列D的头元素，并返回；

Inject(X,D)：将元素X插入到双端队列D的尾部；
Eject(D)：删除双端队列D的尾部元素，并返回。

Push和Inject应该在正常执行完操作后返回true，或者在出现非正常情况时返回false。
当Front和Rear相等时队列为空，Pop和Eject必须返回由裁判程序定义的ERROR。
*/
// 构建双端循环队列
// bool Push( ElementType X, Deque D ) {
//     // 思路：判断队列是否满  实现在插入元素移动Rear指针  
//     if ((D->Rear + 1) % D->MaxSize == D->Front) {
//         retrun false;
//     }
//     D->Data[D->Rear++] = X;
//     return true;
// }
// ElementType Pop( Deque D ) {
//     // 思路：判断是否为空 
//     if (D->Front == D->Rear) {
//         return ERROR;
//     }
//     // 此处应该是先移动 在返回当前值
//     return D->Data[-D->Front];
// }

// 此处理解错了题意 两个指针应该是都可以前后移动的   push pop 主管Front   inject eject  主管Rear
bool Push( ElementType X, Deque D ) {
    // 判断队列是否已满： 向后移动Front指针来使得rear指针相对前移
    // 但此时需要考虑一个新的问题  ：填入再后移还是后移再填入
    // 暂且修改成队头添加元素都是移动在填入  删除元素都是删除再移动
    if ((D->Rear + 1) % (D->MaxSize) == D->Front ) {
        return false;
    }
    D->Front = (D->Front -1 + D->MaxSize) % D->MaxSize;
    D->Data[D->Front] = X;
    return true;
}
ElementType Pop( Deque D ) {
    // 思路：判断是否为空  在删除之后在向前移动Front指针
    // 此处还涉及 返回的顺序问题 必须提前定义一个变量来存取当前元素的值
    ElementType temp ;
    if (D->Front  == D->Rear) {
        return ERROR;
    }
    temp = D->Data[D->Front];
    D->Front = (D->Front + 1) % D->MaxSize;
    return temp;
}

bool Inject( ElementType X, Deque D ) {
    // 在队尾对Rear指针进行操作   填入元素就向后移 弹出元素就向前移 
    // 经过逻辑分析发现 队尾元素要先填入再移动
    if ((D->Rear + 1) % (D->MaxSize) == D->Front ) {
        return false;
    }
    D->Data[D->Rear] = X;
    D->Rear = (D->Rear + 1) % D->MaxSize;
    return true;
}
ElementType Eject( Deque D ) {
    if (D->Front  == D->Rear) {
        return ERROR;
    }
    D->Rear = (D->Rear - 1 + D->MaxSize) % D->MaxSize;
    return D->Data[D->Rear];
}
// 此处关于队列首尾指针的操作没有问题 问题出现在了两个指针在移动过程中  与 MaxSize-1  的界限问题上  指针越界了 没有及时的修正
// 出错原因是把这里与栈的操作搞混  或者说是没有理解队列的两种存储结构